//给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 
//
// 返回所有可能的结果。答案可以按 任意顺序 返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()())()"
//输出：["(())()","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：s = "(a)())()"
//输出：["(a())()","(a)()()"]
// 
//
// 示例 3： 
//
// 
//输入：s = ")("
//输出：[""]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 25 
// s 由小写英文字母以及括号 '(' 和 ')' 组成 
// s 中至多含 20 个括号 
// 
//
// Related Topics 广度优先搜索 字符串 回溯 👍 885 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        int left = 0;
        int right = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                left++;
            }else if(s.charAt(i) == ')'){
                if(left == 0){
                    right++;
                } else {
                    left--;
                }
            }
        }
        bfs(s, 0, left, right);
        return res;
    }

    private void bfs(String s, int start, int left, int right) {
        if(left ==0 && right==0){
            if(isValid(s)){
                res.add(s);
            }
            return;
        }

        for(int i=start; i<s.length() ; i++){
            if(i != start && s.charAt(i) == s.charAt(i-1)){
                continue;
            }
            if( left + right > s.length() - i){
                return;
            }
            String str = s.substring(0, i) + s.substring(i + 1);
            if(left>0 && s.charAt(i)=='('){
                bfs(str, i,left-1, right);
            }
            if(right>0 && s.charAt(i)==')'){
                bfs(str, i, left,right-1);
            }
        }
    }

    private boolean isValid(String s){
        int count = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            } else if(s.charAt(i) == ')'){
                count--;
                if(count < 0){
                    return false;
                }
            }
        }
        return count == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
